The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP). Note, nothing described or referenced in this document is admitted as prior art to this application unless explicitly so stated.
In order for a router or other network device to properly send packets to their respective destinations, forwarding information must be identified for each packet. There are many different known techniques for distributing routing information, with a common one being Border Gateway Protocol (BGP). From this BGP and/or other routing information, packet forwarding information is derived for the device and stored multiple data structures often referred to as forwarding information bases (FIBs). This forwarding information for a particular address may include next hop information (e.g., the address of the next destination to where to send the packet, and the egress interface from which to send the packet), or even include higher-level forwarding information such as that related to virtual local area networks (VLANs), virtual private networks (VPNs), etc., which may require multiple successive lookup operations in multiple FIBs.
Typically, a FIB is implemented in a manner to allow the determination of a longest prefix matching a specified address. There are an unlimited number of known mechanisms for performing lookup operations based on an address to identify a leaf node, such as, but not limited to placing address in an associative memory (e.g., a ternary content-addressable memory), performing a direct or hashed lookup on the address or several strides of the address (i.e., MTRIE, etc.), tree bitmap (e.g., that disclosed in U.S. Pat. No. 6,560,610, issued May, 6, 2003, which is hereby incorporated by reference), compressed prefix matching database searching (e.g., that disclosed in U.S. Pat. No. 5,781,772, issued Jul. 14, 1998, which is hereby incorporated by reference), and an unlimited number of other lookup mechanisms and approaches.
Shown in FIG. 1A is a prior system which uses tree data structures for identifying a longest matching prefix with the leafs (also often referred to as leaf nodes) populated with the prefixes of interest (i.e., as defined by the FIB). As shown, FIG. 1A illustrates one such prior system with two data structures 100 and 102, each used to store a different FIB. These two FIBs, albeit independent, can be used in forwarding a single packet such as by doing sequential lookup operations on them. In a prior system which is the form of multiple virtual routers emulated by a single physical router, FIBs are exclusively used for their respective virtual router, which can require a lot of memory space. In fact, in one implementation in which multiple virtual routers are emulated on a single line card, the line card does not have enough physical memory space required to store all of the desired FIBs simultaneously.
FIG. 1B illustrates a process used in a prior system for identifying forwarding information of a FIB for a packet, such as that using one of the data structures 100 or 102 shown in FIG. 1A. Processing begins with process block 110, and proceeds to process block 112, wherein the destination address is extracted from the received packet. In process block 114, the longest matching leaf node is set to NULL (i.e., no match located). In process block 116, the longest prefix matching tree is traversed until a leaf node is reached. In process block 118, the longest matching leaf node is set to the current leaf node. As determined in process block 120, if the end of the tree has not been reached, then processing returns to process block 116. Otherwise, the leaf node corresponding to the longest matching prefix has been identified, and in process block 122, the packet is forwarded based on the forwarding information stored in this leaf node. Processing is complete as indicated by process block 124.
FIG. 1C illustrates how a prior system which implements networking services which require sequential lookup operations in multiple FIBs. A first lookup operation is performed in data structure-1 (140) to identify the forwarding information of the first FIB, and then a first lookup operation is performed in data structure-2 (142) to identify the forwarding information of the second FIB. Each of these lookup operations requires traversing the longest prefix matching tree. This sequence of FIB lookup operations is further illustrated by the flow diagram of FIG. 1D.
Processing begins with process block 160, and proceeds to process block 162, wherein the destination address of a received packet is extracted. In process block 164, a lookup operation is performed in the first FIB, which includes walking the first tree to find the corresponding leaf node based on the destination address. As determined in process block 165, if the end result has not been determined, then, in process block 166, a next lookup operation is performed in the next FIB, which includes walking the next tree to find the corresponding leaf node based on the destination address. Processing returns to process block 165. After all FIB lookup operations, each including a tree traversal, have been completed, the packet is forwarded according to the end result in process block 168. Processing is complete as indicated by process block 169.